/*
 * Copyright (C) 2008+ Spark Zheng
 *
 * src/test/test_hash.c
 * 
 * do a test with a collection of hash functions 
 * 1. speed.
 * 2. distribution.
 * 3. collision.
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>

#include "timer.h"
#include "hash.h"
#include "htable.h"

/* test digital hashes */
#define U_SCOPE_LEN	100000000U	/* the U-scope */
#define K_SCOPE_LEN	1000000U	/* the keyword scope */

/* test string hashes */
#ifdef BUF_LEN
#undef BUF_LEN
#endif
#define BUF_LEN		1024
#define DICT    "/home/sparkzheng/Projects/mfs_projects/dcache/tmp/dict_utf8"

typedef struct val {
	char		*key;
	uint32_t	visit;
	uint32_t	type;
} S_VAL;

typedef struct acct_timer {
	struct timeval	acct;
	int		type;
} S_ACCT_TIMER;
	

static void _usage(void);
static int _compare(const void *one, const void *two);
static uint32_t _hash(const void *k, void *other);
static void _release_val(void *val);
static void _walker(const void *k, const void *v, void *arg);

static void _usage(void)
{
	fprintf(stdout, "test_hash [dict_len] [hash_type]\n");

	return;
}

static int _compare(const void *one, const void *two)
{
	const char *s_one = (const char *)one;
	const char *s_two = (const char *)two;
	
	while ((*s_one | *s_two) != 0) {
		if (*s_one < *s_two)
			return -1;
		else if (*s_one > *s_two)
			return 1;
		else {
			s_one++;
			s_two++;
		}
	}
	
	return 0;
}

static uint32_t _hash(const void *k, void *other)
{
	uint32_t ret = 0;
	S_ACCT_TIMER *timer = (S_ACCT_TIMER *)other;
	struct timeval start, end, result, all;

	const char *key = (const char *)k;
	uint32_t key_len = strlen(key);

	switch (timer->type) {
		case 1:
			DLIB_UTIMER_RECORD(&start);
			ret = simple_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 2:
			DLIB_UTIMER_RECORD(&start);
			ret = one_at_a_time_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 3:
			DLIB_UTIMER_RECORD(&start);
			ret = elf_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 4:
			DLIB_UTIMER_RECORD(&start);
			ret = ext_dx_hack_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 5:
			DLIB_UTIMER_RECORD(&start);
			ret = glib_string_hash(key);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 6:
			DLIB_UTIMER_RECORD(&start);
			ret = glib_pointer_hash(key);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 7:
			DLIB_UTIMER_RECORD(&start);
			ret = rs_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 8:
			DLIB_UTIMER_RECORD(&start);
			ret = js_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 9:
			DLIB_UTIMER_RECORD(&start);
			ret = sdbm_hash(key);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 10:
			DLIB_UTIMER_RECORD(&start);
			ret = bkdr_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 11:
			DLIB_UTIMER_RECORD(&start);
			ret = djb_hash(key);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 12:
			DLIB_UTIMER_RECORD(&start);
			ret = r5_hash(key);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 13:
			DLIB_UTIMER_RECORD(&start);
			ret = ap_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 14:
			DLIB_UTIMER_RECORD(&start);
			ret = calc_hash(key, key_len);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		case 15:
			DLIB_UTIMER_RECORD(&start);
			ret = perfect_hash(key, key_len, 0);
			DLIB_UTIMER_RECORD(&end);
			DLIB_UTIMER_SUB(&end, &start, &result);
			DLIB_UTIMER_ADD(&timer->acct, &result, &all);
			DLIB_UTIMER_INIT(&timer->acct, all.tv_sec, all.tv_usec);
			break;
		default:
			break;
	}
	
	return ret;
}

static void _release_val(void *val)
{
	S_VAL *t = (S_VAL *)val;
	
	if (t == NULL) return;
	
	if (t->key != NULL) {
		free(t->key);
		t->key = NULL;
	}
	free(t);
	
	return;
}

static void _walker(const void *k, const void *v, void *arg)
{	
	fprintf(stdout, "walker: key is %s, v is %p, arg is %d.\n",
		(const char *)k, v, *(int *)arg);

	(*(int *)arg)++;
	
	return;
}

int main(int argc, char *argv[])
{
	int i = 1;
	uint32_t dict_len = 1113; /* a primer */

	S_ACCT_TIMER timer;
	htable_t *dict;

	FILE *fp;
	
	char buffer[BUF_LEN + 1];
	
	S_VAL *value;
	char *nat = NULL;
	char *key = NULL;
	size_t key_len = 0;
	
	if (argc == 2 && argv[1][0] == '-' && argv[1][1] == 'h') {
		_usage();
		return -1;
	} 

	memset(&timer, 0, sizeof(timer));

	if (argc == 2 && atoi(argv[1]) != 0)
		dict_len = (uint32_t)atoi(argv[1]);
	
	if (argc == 3 && atoi(argv[1]) != 0 && atoi(argv[2]) != 0) {
		dict_len = (uint32_t)atoi(argv[1]);
		timer.type = atoi(argv[2]);
	}

	if (timer.type != 0) {
		dict = ht_init(dict_len, _hash, &timer,  _compare, 0, _release_val);
		if (dict == NULL) {
			fprintf(stderr, "ht_init error.\n");
			return -2;
		}

		if ((fp = fopen(DICT, "r")) == NULL) {
			fprintf(stderr, "fopen error: %s\n", strerror(errno));
			ht_exit(dict);
			return -3;
		}

		fprintf(stdout, "ht_table load ...\n");
		
		memset(buffer, 0, BUF_LEN + 1);
		while (fgets(buffer, BUF_LEN, fp) != NULL) {
			key = strtok(buffer, "\r\n\t ");
			if (key == NULL) continue;
			
			key_len = strlen(key);
			value = (S_VAL *)calloc(1, sizeof(S_VAL));
			value->key = (char *)calloc(1, key_len + 1);
			memcpy(value->key, key, key_len);
			
			value->visit = (uint32_t)atoi(strtok(NULL, "\r\n\t "));
			nat = strtok(NULL, "\r\n\t ");
			value->type = 0;
			
			ht_set(dict, value->key, value);
			
			memset(buffer, 0, BUF_LEN);
		}
		
		fclose(fp);

		fprintf(stdout, "ht_table load successfully.\n");
		fprintf(stdout, "type[%d] time [%06f].\n", timer.type,
			timer.acct.tv_sec + (float)timer.acct.tv_usec / 1000000);
		
		ht_dump(dict);
		ht_exit(dict);
	} else {	
	while (i < 16) {
		memset(&timer, 0, sizeof(timer));
		timer.type = i++;
		dict = ht_init(dict_len, _hash, &timer,  _compare, 0, _release_val);
		if (dict == NULL) {
			fprintf(stderr, "ht_init error.\n");
			return -2;
		}

		if ((fp = fopen(DICT, "r")) == NULL) {
			fprintf(stderr, "fopen error: %s\n", strerror(errno));
			ht_exit(dict);
			return -3;
		}

		fprintf(stdout, "ht_table load ...\n");
		
		memset(buffer, 0, BUF_LEN + 1);
		while (fgets(buffer, BUF_LEN, fp) != NULL) {
			key = strtok(buffer, "\r\n\t ");
			if (key == NULL) continue;
			
			key_len = strlen(key);
			value = (S_VAL *)calloc(1, sizeof(S_VAL));
			value->key = (char *)calloc(1, key_len + 1);
			memcpy(value->key, key, key_len);
			
			value->visit = (uint32_t)atoi(strtok(NULL, "\r\n\t "));
			nat = strtok(NULL, "\r\n\t ");
			value->type = 0;
			
			ht_set(dict, value->key, value);
			
			memset(buffer, 0, BUF_LEN);
		}
		
		fclose(fp);

		fprintf(stdout, "ht_table load successfully.\n");
		fprintf(stdout, "type[%d] time [%06f].\n", timer.type,
			timer.acct.tv_sec + (float)timer.acct.tv_usec / 1000000);
		
		ht_dump(dict);
		ht_exit(dict);
	} }

	return 0;
}
